package lib

import "math"

//link to 264
func init() {
	Probs = append(Probs, Problem{
		Num:         313,
		Discription: "给定质数集的丑数",
		Level:       2,
		Labels: map[string]int{
			"动态规划":    1,
			"数学": 1,
		},
	})
}

func NthSuperUglyNumber(n int, primes []int) int {
	primeMap := make(map[int]int,len(primes))
    for _,prime:=range primes{
        primeMap[prime]=0
    }

	dp := make([]int, n)
	dp[0] = 1
	for i := 1; i < n; i++ {
		dp[i] = math.MaxInt32
		for prime, index := range primeMap {
			dp[i] = min(dp[i], prime*dp[index])
		}
		for prime, index := range primeMap {
			if prime*dp[index] == dp[i] {
				primeMap[prime]++
			}
		}
	}

	return dp[n-1]
}